package 数据结构考纲.测试;

import 力扣.公用数据结构.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Tree {

    int max_high = 0;

    //获得孩子兄弟表示的树的高度
    void getHeight(TreeNode root, int h) {
        if (root == null)
            return;
        max_high = Math.max(max_high, h);
        if (root.left != null)
            getHeight(root.left, h + 1);
        if (root.right != null)
            getHeight(root.right, h);
    }

    void height(TreeNode tree) {

        if (tree == null)
            System.out.print("树的高度为0");
        getHeight(tree, 1);
        System.out.printf("树的高度为：" + max_high);
    }

    //获得根到某节点的路径
    int[] path = new int[100];
    int len = 0;

    void getPath(TreeNode root, int x) {
        if (root == null) {
            return;
        } else if (root.val == x) {
            path[len++] = x;
            for (int i = 0; i < len; i++) {
                System.out.printf("%d ", path[i]);
            }
            System.out.println();
            return;
        }
        path[len++] = root.val;
        getPath(root.left, x);
        getPath(root.right, x);
        len--;  //右子树为空再减路径长度
    }

    //第N层权值之和
    int getKSum(TreeNode root, int k) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int d = 0;//第几层
        queue.add(root);
        while (!queue.isEmpty()) {
            int sum = 0;
            int size = queue.size();//当前层数量
            while (size-- > 0) {
                TreeNode poll = queue.poll();
                sum += poll.val;
                if (poll.left != null)
                    queue.add(poll.left);
                if (poll.right != null)
                    queue.add(poll.right);
            }
            d++;
            if (d == k)
                return sum;
        }
        return 0;//没有第k层
    }


    public static void main(String[] args) {
        TreeNode tree1 = TreeNode.stringToTreeNode("[1,2,null,null,5,null,null,null,null,10]");
        TreeNode tree2 = TreeNode.stringToTreeNode("[1,2,null,null,5,null,null,null,null,10]");
        //层序遍历建立
        TreeNode tree3 = TreeNode.stringToTreeNode("[1,2,null,null,5,10]");
        TreeNode tree4 = TreeNode.stringToTreeNode("[1,2,null,4,5,null,null,10]");
        TreeNode tree5 = TreeNode.stringToTreeNode("[1,2,null,null,5]");
        TreeNode tree6 = TreeNode.stringToTreeNode("[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]");
        Tree tree = new Tree();
        tree.height(tree3);

        TreeNode tree7 = TreeNode.creat("[0,1,2,null,4,null,6,null,null,9]");
        System.out.println("\n根到x的路径");
//        test1.getPath(tree6,19);
        tree.getPath(tree7, 9);
        int kSum = tree.getKSum(tree7, 4);
        System.out.printf("第k层权值和"+kSum);
    }
}
